package com.monkeyboy.stack;

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Stack;

/**
 * 滑动窗口的最大值
 * 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。
 * 例如，如果输入数组 {2, 3, 4, 2, 6, 2, 5, 1} 及滑动窗口的大小 3，那么一共存在 6 个滑动窗口，他们的最大值分别为 {4, 4, 6, 6, 6, 5}。
 * <p>
 * 解题思路：
 * 窗口使用一个堆来进行管理，然后依次从数组里面获取下标取值放入堆里面
 *
 * @Author Gavin
 * @date 2021.04.01 11:12
 */
public class Stack06 {
    public ArrayList<Integer> getMax(int[] num, int size) {
        ArrayList<Integer> result = new ArrayList<>();
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for (int i = 0; i < size; i++) {
            queue.add(num[i]);
        }
        result.add(queue.peek());
        for (int i = 0, j = size + i; j < num.length; i++, j++) {
            queue.remove(num[i]);//这里是remove，不是poll,移除指定元素
            queue.add(num[j]);
            result.add(queue.peek());
        }
        return result;
    }

    public static void main(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.add(1);
        queue.remove();
        System.out.println(queue.poll());
    }
}
